#ifndef DSU_H_
#define DSU_H_
/******Disjoint Set Union(并查集)******/

#include <algorithm>
#include <unordered_map>
#include <vector>

namespace lxj
{
// 移除最多的同行或同列石头
// n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头
// 如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头
// 给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置
// 返回 可以移除的石子 的最大数量。
// 测试链接 : https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/
class MostStonesRemovedWithSameRowOrColumn {
    std::unordered_map<int, int> rowFirst, colFirst;
    inline constexpr static int  MAXN         = 1001;
    inline static int            father[MAXN] = {};
    inline static int            sets         = 0;

public:
    inline int find(int i)
    {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    inline bool isSameSet(int a, int b) { return find(a) == find(b); }

    inline void unionSet(int a, int b)
    {
        int fx = find(a);
        int fy = find(b);
        if (fx != fy) {
            father[fx] = fy;
            sets--;
        }
    }

    inline void build(int n)
    {
        sets = n;
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }

    inline int removeStones(std::vector<std::vector<int>>& stones)
    {
        rowFirst = std::unordered_map<int, int>();
        colFirst = std::unordered_map<int, int>();
        int n    = stones.size();
        build(n);
        for (int i = 0; i < n; i++) {
            int x = stones[i][0];
            int y = stones[i][1];
            if (rowFirst.count(x) == 0)
                rowFirst.insert({x, i});
            else
                unionSet(i, rowFirst[x]);

            if (colFirst.count(y) == 0)
                colFirst.insert({y, i});
            else
                unionSet(i, colFirst[y]);
        }
        return n - sets;
    }
};

// 找出知晓秘密的所有专家
// 给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号
// 另外给你一个下标从 0 开始的二维整数数组 meetings
// 其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会
// 一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson
// 专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson
// 接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播
// 更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密
// 那么他将会与专家 yi 分享这个秘密，反之亦然。秘密共享是 瞬时发生 的
// 也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享
// 在所有会议都结束之后，返回所有知晓这个秘密的专家列表
// 你可以按 任何顺序 返回答案
// 链接测试 : https://leetcode.cn/problems/find-all-people-with-secret/
class FindAllPeopleWithSecret {
    inline constexpr static int MAXN         = 100001;
    inline static int           father[MAXN] = {};
    inline static bool          secret[MAXN] = {};

    inline void build(int len, int firstPerson)
    {
        for (int i = 0; i < len; i++) {
            father[i] = i;
            secret[i] = false;
        }
        father[firstPerson] = 0;
        secret[0]           = true;
    }

    inline int find(int i)
    {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    inline void unionSet(int a, int b)
    {
        int fx = find(a);
        int fy = find(b);
        if (fx != fy) {
            father[fx] = fy;
            secret[fy] |= secret[fx];
        }
    }

public:
    inline std::vector<int> findAllPeople(int                            n,
                                          std::vector<std::vector<int>>& meetings,
                                          int                            firstPerson)
    {
        build(n, firstPerson);
        int len = meetings.size();
        std::sort(meetings.begin(), meetings.end(), [](auto& a, auto& b) { return a[2] < b[2]; });
        for (int l = 0, r; l < len;) {
            r = l;
            while (r + 1 < len && meetings[l][2] == meetings[r + 1][2]) r++;
            for (int i = l; i <= r; i++) {
                unionSet(meetings[i][0], meetings[i][1]);
            }
            for (int i = l, a, b; i <= r; i++) {
                a = meetings[i][0];
                b = meetings[i][1];
                if (!secret[find(a)]) father[a] = a;
                if (!secret[find(b)]) father[b] = b;
            }
            l = r + 1;
        }

        std::vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (secret[find(i)]) ans.push_back(i);
        }
        return ans;
    }
};

// 好路径的数目
// 给你一棵 n 个节点的树（连通无向无环的图）
// 节点编号从0到n-1，且恰好有n-1条边
// 给你一个长度为 n 下标从 0 开始的整数数组 vals
// 分别表示每个节点的值。同时给你一个二维整数数组 edges
// 其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边
// 好路径需要满足以下条件：开始和结束节点的值相同、 路径中所有值都小于等于开始的值
// 请你返回不同好路径的数目
// 注意，一条路径和它反向的路径算作 同一 路径
// 比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径
// 测试链接 : https://leetcode.cn/problems/number-of-good-paths/
class NumberOfGoodPaths {
    inline constexpr static int MAXN         = 30001;
    inline static int           father[MAXN] = {};
    inline static int           maxcnt[MAXN] = {};

    inline void build(int len)
    {
        int i = 0;
        std::transform(father, father + len, father, [&i](int) { return i++; });
        std::fill(maxcnt, maxcnt + len, 1);
    }

    inline int find(int i)
    {
        if (i != father[i]) father[i] = find(father[i]);
        return father[i];
    }

    inline int unionSet(int a, int b, const std::vector<int>& vals)
    {
        int fx   = find(a);
        int fy   = find(b);
        int path = 0;
        if (vals[fx] > vals[fy]) {
            father[fy] = fx;
        }
        else if (vals[fx] < vals[fy]) {
            father[fx] = fy;
        }
        else {
            path       = maxcnt[fx] * maxcnt[fy];
            father[fy] = fx;
            maxcnt[fx] += maxcnt[fy];
        }
        return path;
    }

public:
    inline int numberOfGoodPaths(std::vector<int>& vals, std::vector<std::vector<int>>& edges)
    {
        int len = vals.size();
        build(len);
        std::sort(edges.begin(), edges.end(), [&vals](std::vector<int>& e1, std::vector<int>& e2) {
            return std::max(vals[e1[0]], vals[e1[1]]) < std::max(vals[e2[0]], vals[e2[1]]);
        });
        int ans = len;
        for (auto& e : edges) {
            ans += unionSet(e[0], e[1], vals);
        }
        return ans;
    }
};

// 尽量减少恶意软件的传播 II
// 给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示
// 在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。
// 一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，
// 且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。
// 这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
// 假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
// 我们可以从 initial 中删除一个节点，
// 并完全移除该节点以及从该节点到任何其他节点的任何连接。
// 请返回移除后能够使 M(initial) 最小化的节点。
// 如果有多个节点满足条件，返回索引 最小的节点 。
// initial 中每个整数都不同
// 测试链接 : https://leetcode.cn/problems/minimize-malware-spread-ii/
class MinimizeMalwareSpreadII {
    inline constexpr static int MAXN        = 301;
    inline static bool          virus[MAXN] = {};

    // 每个源头点删掉的话，能拯救多少点的数据
    inline static int cnt[MAXN] = {};

    // 集合的标签 : 集合的感染点是什么点
    // a : 代表点，整个集合源头是 infect[a]
    // infect[a] == -1，目前这个集合没有发现源头
    // infect[a] >= 0，目前这个集合源头是 infect[a]
    // infect[a] == -2，目前这个集合源头不止一个，已经无法拯救了!
    inline static int infect[MAXN] = {};

    inline static int father[MAXN] = {};

    // 集合的标签 : 集合的大小是多少
    inline static int size[MAXN] = {};

    inline void build(int len, const std::vector<int>& initial)
    {
        for (int i = 0; i < len; i++) {
            virus[i]  = false;
            cnt[i]    = 0;
            infect[i] = -1;
            size[i]   = 1;
            father[i] = i;
        }
        for (int i : initial) {
            virus[i] = true;
        }
    }

    inline int find(int i)
    {
        if (i != father[i]) father[i] = find(father[i]);
        return father[i];
    }

    inline void unionSet(int a, int b)
    {
        int fx = find(a);
        int fy = find(b);
        if (fx != fy) {
            father[fx] = fy;
            size[fy] += size[fx];
        }
    }

public:
    int minMalwareSpread(std::vector<std::vector<int>>& graph, std::vector<int>& initial)
    {
        int len = graph.size();
        build(len, initial);

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (graph[i][j] == 1 && !virus[i] && !virus[j]) {
                    unionSet(i, j);
                }
            }
        }

        for (int sick : initial) {
            for (int ner = 0; ner < len; ner++) {
                if (sick != ner && !virus[ner] && graph[sick][ner] == 1) {
                    int fn = find(ner);
                    if (infect[fn] == -1) {
                        infect[fn] = sick;
                    }
                    else if (infect[fn] != -2 && infect[fn] != sick) {
                        infect[fn] = -2;
                    }
                }
            }
        }

        for (int i = 0; i < len; i++) {
            if (i == find(i) && infect[i] >= 0) {
                cnt[infect[i]] += size[i];
            }
        }
        std::sort(initial.begin(), initial.end());
        int ans = initial[0];
        int max = cnt[ans];
        for (int i : initial) {
            if (cnt[i] > max) {
                ans = i;
                max = cnt[i];
            }
        }
        return ans;
    }
};
}   // namespace lxj

#endif